The present invention relates to a router for use in fabricating integrated circuit chips, and, more specifically, a subgrid detailed router
In the art of integrated chip layout, routing is the term used describe placing wires into locations on an integrated circuit chip. There are two conventional approaches to detailed routing, which are grid based routing systems, and gridless routing systems.
Prior to discussing detailed routing, it is helpful to put in context the overall design steps that are conventionally implemented when fabricating the physical design of an integrated circuit chip using a physical design system. As illustrated in FIG. 1, the overall design flow of the physical design includes receiving a cell level netlist, as shown in step 2. Thereafter, this cell level netlist is used to determine the placement of modules that exist within the netlist into locations on the chip, shown as step 4. Modules will contain information relating to a combination of logical functions, and will include the pin and obstacle information needed for routing purposes. The netlist will also contain information relating to the various different pins that need to be interconnected. Thereafter, in a global routing step 6, a global routing grid (which may have been implemented in the placement step), is used to route various wires between pins of modules that traverse paths over several global routing grids. In a following detailed routing step 8, a detailed routing grid (or simply routing grid hereafter) is implemented, typically at a higher resolution than the previously discussed global routing grid, and the detailed placement of wires is performed. The output of the detailed routing step 8 is an integrated circuit fabrication mask.
In a conventional grid based detailed routing system, each of the different layers of an integrated circuit chip is represented in the detailed routing grid. The detailed routing grid is a 3D representation, with each of the different layers of the integrated circuit needed for routing purposes having a uniform area that is subdivided into the routing grids previously discussed, thereby forming a grid pattern for each layer. FIG. 2A illustrates one layer of such a 3D routing grid, in which that layer is subdivided into a grid pattern 10 having separate grids 12 of uniform size. This uniform size of the grids 12 is typically determined by the minimum width of the wires that can be obtained plus the minimum spacing that must be maintained between adjacent wires and/or vias.
The 3D routing grid will have layers corresponding to the different routing layers. As shown in FIG. 2B, a typical integrated circuit will have at least a semiconductor layer, and three wiring layers, such as HVH wiring layers, which stands for horizontal, vertical and horizontal wiring. In HVH wiring, one wiring layer (H1) is generally used to make horizontal traversals, another wiring layer (V) is generally used to make vertical traversals, and another layer (H2) is generally used to make horizontal traversals. Using these different wiring layers, and vias that interconnect adjacent layers together, pins of modules that need to be interconnected can be connected together using the 3D routing grid.
When performing detailed routing, the detailed router receives chip technology description data and data that has been generated as a result of the global routing step, which describe data including the number of layers (levels) on which rectangles representing wires can be generated, the minimum allowed width of any part of the path of rectangles, and the minimum allowed separation between any non-electrically-connected rectangles, as is conventionally known.
In detailed routing, data associated with the various modules is received. For detailed routing purposes, the detailed router interprets this information either as a pin or an obstacle. For any set of pins being interconnected, those pins are not obstacles, but other pins, and other wires that have been previously generated, as well as other obstacles, must be avoided in order to avoid a short circuit. Each of these pins and obstacles is represented as a set of rectangular shapes and will have an associated position and associated layer that is maintained in the database.
Various conventions are used for the representation of pins, wires (or nets) and obstacles in a grid. A common conventionxe2x80x94called the centerline conventionxe2x80x94is that the grid describes the acceptable location for the centerline of the paths that is used during the expansion process to determine the path of a net. When a net is routed, the path must stay away from existing obstacles, such as other wires, vias, and pins of other nets that have been previously placed in the 3D routing grid. In order to stay away from these obstacles, they are modeled by marking certain grid points as invalid. Thus, every intersection of the horizontal and vertical equidistant gridlines is tracked as a position to which the center of a square of a net to be routed may be assigned when legal. Such an assignment is legal if the square centered on the grid point has legal separation with respect to all other rectangles not associated with the net currently being routed. It may require traversals over several proposed paths before a successful traversal results in a placement location being found
FIG. 3. illustrates a representation of a portion of a routing grid and the obstacles and pins associated therewith. As can be seen, associated with one module are pins 12A and 12b, and obstacles 14A and 14B. Associated with another module are Pins 12C and 12D; and obstacles 14C and 14D. Furthermore, the region marked 14E shows the interconnection of the pins 12B and 12C. Thus, for interconnections of other nets, the region marked 14E will also be an obstacle.
Using a list of the different pins that need to be connected, the detailed router will traverse a path from the initial pin location (such as pin 12B in FIG. 3, to an endpoint pin location (such as pin 12C In reply to FIG. 3). It should be noted that in many cases, there exist many different possible connection locations to which the endpoint pin location can legally go, and once the detailed router finds a first such endpoint pin location, it has completed its task for that net, and will then move onto routing the next net. It should be noted that provision is also made for routing vias that connect conductors that exist at different adjacent levels and are used to form a single wire.
With that background description of grid based routing in mind, it will be appreciated that detailed routing grids are represented as a set of grid points and a set of edges between adjacent grid points. A so-called cost value is associated with every edge. Thus, detailed routing is a combinatorial optimization with the objective being to find a path of vertices between not yet connected features that are part of the net, including its pins. One manner in which to find the path between two points in a grid (such as two pins of different modules that need to be connected) can be found using a shortest path algorithm such as Dijkstra""s shortest path algorithm. Routers that operate in the above-described manner are known as Lee-type routers.
In a detailed router, obstacle and wire congestion modeling analyses are also used in grid based routing systems to increase the likelihood that the particular wire placement determined during the global routing stage can actually be implemented at a finer level (i.e., within a portion of the grid in which it was placed). However, regardless of the effort put into these modeling techniques, they are either too optimistic at the expense of routing completion or too pessimistic at the expense of density. Thus, as integrated circuits become more complex and deep submicron designs proliferate, conventional grid based routing systems are not able to implement all of the design requirements. For example, in deep submicron designs, it is desirable to have wires having different and non-uniform widths and spacings. While a grid based routing system will permit different and non-uniform wire widths and spacings in certain circumstances, the constraints that occur as a result make it undesirable to implement different and non-uniform wire widths and spacings in such systems.
From the above description, it will also be apparent that the choice of the routing grid is extremely important, as it affects the packing efficiency, which measures how tightly the wires can be packed, with the constraint that the centerlines of the wires are on the chosen grid, compared to the packing in a gridless world. Suppose the width and spacing are both 0.4 xcexcm (0.4 microns) on all layers, as illustrated in FIGS. 4A and 4B. Then a natural routing grid has track separations of 0.8 xcexcm (both horizontally and vertically) as illustrated in FIG. 4C, and adjacent wires can be packed at 100% packing efficiency. However, if the routing grid is chosen to be 0.6 xcexcm or 1.2 xcexcm, as illustrated in FIGS. 4D and 4E, then the wires can only be packed at 66% packing efficiency. If the routing grid is chosen to be 0.4 xcexcm, the wires can be maximally packed at 100%, but the size of the grid is quadrupled (doubled in each direction).
Accordingly, when width and spacing on different layers and different wires exists, the choice of the routing grid becomes even more difficult, as it will have a direct impact on the packing efficiency. In practice, existing grid-based routers require the routing grid, as well as the width and spacing of all nets to be chosen a priori, and are not subjected to change. When there are a variety of net-dependent width and spacing requirement, often time the worst-case values are chosen. The loss in packing efficiency due to improper matching between the routing grid and the width and spacing is called fragmentation. The process of determining the correct width (per layer), spacing (per layer), and routing grid to be used throughout routing is called pitch matching. Poor pitch matching results in significant degradation in quality and runtime of grid-based maze routing algorithms.
Also, one of the significant constraints on grid based routing systems, particularly for more complex designs, is the time that it takes to perform routing. When designs were simpler, the size of the gridxe2x80x94the separation between adjacent grid pointsxe2x80x94could be made relatively large, and, therefore, the time that it took to determine traversal paths was relatively short. Thus, for less complex semiconductor designs, grid based routing systems have been adequate and routing completion was obtained within acceptable time periods.
As designs have become more complex, however, it is not a simple matter to just reduce the size of the grid, since reducing the size of the grid brings with it a significant increase in the number of grid points, and hence a significant increase in the time needed to traverse a path. For instance, by taking a grid that was previously a single grid square per unit area and making that same grid square a quadruple in both the horizontal and vertical dimensions, thereby resulting in a grid having the resolution illustrated in FIG. 5. As compared to FIG. 2A, this results in a 16X increase in the number of grid points, and hence a significant increase in the runtime of the maze router used to determine a path. Such an increase in time is not a practical solution, since designers are unwilling to wait such long periods in order for the routing to occur.
The other approach that has been used for routing is known as a gridless routing system. As it is implied by the name gridless, such routing does not use a grid for routing, but instead keeps track of all of the obstacles based upon their location with respect to each other. Such a gridless routing system theoretically has as an advantage in that it can find a path that does not have to adhere to a predefined routing grid, as in the case of a grid-based router. While this theoretical advantage exists, such systems are technically complex and complicated, do not typically perform as well as expected, and are typically slow, especially as the integrated circuit that is being routed becomes more and more complex.
As a result of the complexity of gridless routing systems, attempting to modify them to perform even more sophisticated design requirements is not practicable.
Accordingly, a routing system that can correctly route a path in a reasonable period of time is still needed.
It is an object of the present invention to implement a router that can efficiently route wires that have variable widths and spacings.
It is an object of the present invention to implement a router that has the efficiency of a conventional maze router for path expansion;
It is an object of the present invention to implement a router that has greater resolution than conventional grid based routers while not requiring an increase in runtime as compared to conventional grid based routers.
It is a further object of the invention to implement a router that guarantees a path exists at a finer subgrid level once a traversal path determined at the grid level is found.
It is still a further object of the present invention to provide for an increased probability that there exists an adequate pitch match between adjacent layers.
It is yet another object of the present invention to be able to more efficiently operate upon obstacles that have edges that do not fall on grid level boundaries.
The present invention attains the above-recited objects of the present invention, among others, by implementing a detailed subgrid router that performs searches for wire locations at the grid level. Once a solution is found, the wire representation is made based upon a finer subgrid. Due to the manner in which the search is performed at the grid level, the present invention guarantees that a path for that wire will exist at the finer subgrid level. The rectangles representing the wire is then stored in the database that includes the other corresponding information, so that it can be treated as an obstacle when routing a subsequent wire. Specifically, the present invention includes subgrids that in a preferred embodiment have a resolution that is 16X greater than the resolution of the conventional grids. This increased resolution is useful for improving routing density with variable width and variable spacing designs.
In operation, the subgrid detailed router of the present invention searches at the grid level for potential wire paths using a code associated with each grid. This code contains data corresponding to each of the subgrids, such that upon completion of a routing a net, information exists that allows for the placement of the net at locations corresponding to the subgrid that has finer resolution than the grid which was used to implement the routing search. Thus, the present invention is as efficient as conventional grid based routers in finding an appropriate path.